package chapter7;

/**
 * 只用位运算不用算数运算实现整数的加减乘除运算
 */
public class ArithmeticOperation {
    // 只用位运算实现加法运算
    public static int add(int a, int b) {
        int sum = 0;
        while (b != 0) {
            sum = a ^ b; // 无进位相加
            b = (a & b) << 1; // 只考虑进位
            a = sum;
        }
        return sum;
    }

    // 只用位运算实现减法操作
    // a-b=a+(-b)
    public static int minus(int a, int b) {
        return add(a, negNum(b));
    }

    // 只用位运算求相反数
    private static int negNum(int n) {
        return add(~n, 1); // 按位取反+1
    }

    // 只用位运算实现乘法
    // a*b=a*2^0*b0+a*2^1*b1+...+a*2^31*b31
    // a左移一位不断乘以2，b不断右移一位&1取第i位
    public static int multi(int a, int b) {
        int res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res = add(res, a);
            }
            a <<= 1;
            b >>= 1;
        }
        return res;
    }

    public static boolean isNeg(int n) {
        return n < 0;
    }
    // 只用位运算实现除法
    //  其实是乘法的逆运算
    // 但本方法前两行不能转换最小值
    public static int div(int a, int b) {
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        int res = 0;
        for (int i = 31; i > -1; i = minus(i, 1)) {
            if ((x >> i) >= y) {
                res |= (1 << i); // 按位或 ，其实这里就是相加
                x = minus(x, y << i);
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }

    // 只用位运算求除法
    public static int divide(int a, int b) {
        if (b == 0) {
            throw new RuntimeException("divisor is 0");
        }
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 1;
        } else if (b == Integer.MIN_VALUE) {
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            int res = div(add(a, 1), b);
            return add(res, div(minus(a, multi(res, b)), b));
        } else {
            return div(a, b);
        }
    }
}














